package main

import "fmt"

func main() {
	arr := []int{-3, 1, 2, -2, 2, -1}

	sum := countRangeSum(arr, -3, -1)
	fmt.Println(sum)
}
func countRangeSum(nums []int, lower int, upper int) int {

	if nums == nil || len(nums) == 0 {
		return 0
	}

	sums := make([]int, len(nums))

	sums[0] = nums[0]
	for i := 1; i < len(sums); i++ {
		sums[i] += sums[i-1] + nums[i]
	}
	fmt.Println(sums)

	return count1(sums, 0, len(sums)-1, lower, upper)
}

func count1(sums []int, l int, r int, lower int, upper int) int {

	if l == r {
		if sums[l] >= lower && sums[l] <= upper { //这个是返回以0开头的所有前缀和数组的单独比较所以直接和lower，upper比较就好
			return 1
		} else {
			return 0
		}
	}

	mid := (r + l) / 2
	leftCount := count1(sums, l, mid, lower, upper)
	rightCount := count1(sums, mid+1, r, lower, upper)

	return leftCount + rightCount + merge5(sums, l, mid, r, lower, upper)
}

func merge5(sums []int, l int, mid int, r int, lower, upper int) int {

	ans := 0
	PointL := l
	PointR := l
	//要分成左右两个区间

	for i := mid + 1; i <= r; i++ {
		min := sums[i] - upper
		max := sums[i] - lower

		for PointR <= mid && sums[PointR] <= max {
			PointR++
		}
		for PointL <= mid && sums[PointL] < min { //防止两个数相同的时候分辨不出来，如果他小于等于的时候遇到[0,0]的时候L,R就会同时移动到第二位导致两个指针重合不能输出有效的1
			PointL++
		}
		fmt.Println(PointL, PointR)
		ans += PointR - PointL
		//PointR L不用重置的原因是因为归并排序的存在左右组整体都是递增的
		//所以符合上一个右组元素的左组肯定也符合当前右组元素整体是往右移而不会回退
	}

	helparr := make([]int, r-l+1)
	i := 0
	p1 := l
	p2 := mid + 1

	for p1 <= mid && p2 <= r {
		if sums[p1] <= sums[p2] {
			helparr[i] = sums[p1]
			p1++
			i++
		}

		if sums[p2] < sums[p1] {
			helparr[i] = sums[p2]
			p2++
			i++
		}

	}

	if p1 > mid {
		for p2 <= r {
			helparr[i] = sums[p2]
			p2++
			i++
		}
	}

	if p2 > r {
		for p1 <= mid {
			helparr[i] = sums[p1]
			p1++
			i++
		}
	}

	for i := 0; i < len(helparr); i++ {
		sums[l+i] = helparr[i]
	}

	return ans
}
